There are many applications which require integrated circuit with configurable interconnect networks. One such application is a FPGA (Field Programmable Gate Array) where logic gates are to be connected to each other by programmable interconnect networks. Functioning either as a stand-alone chip or as a core part in a system, FPGA has been widely used in numerous microelectronic devices. The FPGA logic gate is generally defined to be not only a simple NAND gate, but also a logic cell having combinational logic and timing logic comprising configurable function, or a logic block formed by interconnecting a plurality of the logic cells.
A prior art interconnect network for field programmable (FP) logic cell array is of tree-based hierarchical architecture, in which logic cells are in the lowest level of the tree, and are interconnected with each other through hierarchical switch box (referred to as HSB) located at other joints of the tree topology. The hierarchical interconnect architecture has brought forth high efficiency and scalability in interconnection network.
However, in the tree structure, physical distance and logic distance between two HSBs are two different concepts, and may sometimes be completely inconsistent. Here, ‘logical’ is a term redefined in the context of tree structure, and logical distance is defined in term of number of switch boxes traversed or number of edges traversed when going up and down the tree from one switch box to another one. For example, two HSBs are physically near with each other but need to traverse a number of HSBs to reach each other. Such a tree structure may lead to delay in timing, especially for those in physically neighborhood. Also, the tree-structured interconnect network may be sensitive to logic layout. A change in logic layout may lead to change of wirings between logics, which might unfavorably affect overall logic timing.